#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <assert.h>

int cmp(const void * l,const void * r ){
	return *(int*)l-*(int*)r;
}


void movea(int * data,int from ,int to){
	assert(from>to);
	//in to~from move back 1
	int ff=data[from];
	int i=from;
	for(;i>to;i--){
		data[i]=data[i-1];
	}
	data[to]=ff;
}

void swapa(int* data,int a,int b){
	int ff=data[b];
	data[b]=data[a];
	data[a]=ff;
}

void bubble_sort(int* data,int size){
	int i=1;
	int j=size;
	for(;j>0;j--){
		for(i=1;i<j;i++){
			if(data[i] < data[i-1]){
				swapa(data,i,i-1);
			}
		}
	}
}

void insert_sort(int* data,int size){
	int i=1;
	for(;i<size;i++){
		int next=data[i];
		int j=0;
		int swapped=0;
		for(;j<i;j++){
			if(next<data[j]){
				//put next front of j
				movea(data,i,j);
				swapped=1;
				break;
			}
		}
	}
}

int patition(int* data,int low,int high){
	int st=data[low];
	int j=high;
	int i=low;
	while(j>i){
		for(;j!=i;j--){
			if(data[j] < st){
				swapa(data,j,low);
				break;
			}
		}
		for(;j!=i;i++){
			if(data[i] > st){
				swapa(data,i,j);
				break;
			}
		}
	}
	return i;
}

int patition2(int* data,int low,int high){
	if(low<=high){
		return low;
	}
	swapa(data,low,(low+high)/2);
	int last=low;
	int i;
	for(i=low+1;i<=high;i++){
		if(data[i] < data[low]){
			swapa(data,++last,i);
		}
	}
	swapa(data,low,last);
	return last;
}

void myqsort(int* data,int size,int low,int high){
	if(high<=low)
		return;
	int pos=patition(data,low,high);
	myqsort(data,size,low,pos);
	myqsort(data,size,pos+1,high);	
}

#define ARRAY_SIZE 10
int main(int argc,char** argv)
{
    int data[]={50,23,33,55,11,2,234,102,779,3};

	time_t st=time(NULL);
	if(argc==1){
		printf("qsort\n");
		qsort(data,10,sizeof(int),cmp);
	}else if(argc==2){
		printf("insert_sort\n");
		insert_sort(data,10);
	}else if(argc==3){
		printf("bubble sort\n");
		bubble_sort(data,10);
	}else if(argc==4){
		printf("myqsort	 sort\n");
		myqsort(data,10,0,9);
	}
//	sleep(1);
	time_t end=time(NULL);
	printf("%d,%d clock:%d\n",st,end,clock());
//	clock_t st=clock();
//	clock_t end=clock();
//	printf("time:%d\n",st);
	int i=0;
	for(;i<ARRAY_SIZE;i++){
		printf("%d\t",data[i]);
	}
    exit(EXIT_SUCCESS);
}